최대 플로우 문제(Maximum Flow problem)

용량 제약 조건을 위반하지 않으면서, 물질을 출발점에서 도착점까지 운송할 수 있는 최대 비율

플로우 네트워크(Network Flow)

G(V, E)는 각 간선 (u, v)\in E가 음이 아닌 용량 c를 갖는 방향 그래프

c(u,v)≥0 $c(u, v)\geq 0$ (u,v)∉E $(u, v)\notin E$ 인 경우, c(u,v)=0 $c(u, v)=0$ 플로우(Flow) f:V×V→ℝ $f: V\times V\rightarrow \mathbb{R}$ |f|=Σv∈Vf(s,v)−Σv∈Vf(v,s) $|f|=\Sigma_{v\in V}f(s, v)-\Sigma_{v\in V}f(v, s)$

- 용량 제약 조건: 0<=f(u, v)<=c(u, v)

- 플로우 보존( just like Kirchhoff’s Current Law )

시작점 도착점을 제외한 u∈V−s,t $u\in V-{s, t}$ 에 대해서 |f|=0 $|f|=0$ 을 만족

역평행(antiparallel)

플로우 네트워크에서 역평행 간선

(v1, v2)\in E & (v2, v1)\in E를 허용하지 않는다.

역평행 간선이 존재하는 경우, 역평행 간선이 포함되지 않으며

동등한 그래프 연결을 위해 새로운 정점을 이용한다.

(v1, v2) -> (v1, v’) + (v’, v2)

다중 출발점 & 다중 도착점

단일 출발점과 단일 도착점을 가지는 플로우 문제에서 다중 출발점이 주어지는 경우,

가상 출발점(supersource)와 용량 c(s, s_i)=\infty를 이용한다.

(가상 도착점; supersink)도 c(t_i, t)=\infty를 이용함)